package ua.mykola.graph;

import java.util.LinkedList;
import java.util.Queue;

public class BFS extends FirstSearch {
	private Queue<Edge> queue = new LinkedList<Edge>();

	public BFS(Graph graph, String vertexLabel) {
		super(graph, vertexLabel);
	}

	public BFS(Graph graph, Vertex vertex) {
		super(graph, vertex);
	}

	@Override
	protected void traverse(Vertex vertex) {
		visited.add(vertex);
		for (Edge edge : graph.getEdgesFrom(vertex)) {
			Vertex otherSide = edge.getOtherSide(vertex);
			if (!visited.contains(otherSide)) {
				queue.offer(edge);
				pathUp.put(otherSide, edge);
			}
		}
		while (queue.size() > 0) {
			traverse(queue.poll().getOtherSide(vertex));
		}
	}

}
